There are numerous known methods for searching for data in a data structure stored in a memory of a computer system to find a particular item of information. It is desirable to implement methods for organizing and searching for data in the data structure in a way that reduces the amount of memory required to store the data and perform the search in a more efficient manner.
A table or a file is a group of data elements, each of which may be called an entry or a record in the table. Generally, a key is associated with each record. The key is used to differentiate among different records. The key associated with a particular record may or may not need to be unique, depending on the search method utilized in accessing the table. In addition, the key may or may not be embedded within the record itself.
A search method accepts a key value as input and attempts to locate a record within a table stored in the memory of a computer system whose associated key is the key value. The search method may return a record, or a pointer to the record. The contents of the record may be data, program code, or a pointer to either data or program code. If the search of a table is unsuccessful in finding the key, then there is no record in the table associated with the key value. Typically, if the search is unsuccessful, an insertion is performed to add a new record with the key value as its key.
A table is stored in a data structure in the, memory or an external storage, e.g., magnetic disk, of a computer system. The form of the data structure may be an array of records, a tree, a linked list, etc. Certain search methods are generally more applicable to one form and location of a data structure than another. Thus, the data structure in which a table is stored is, in part, selected according to the search method to be used to access information within the table. The present invention is related to search operations on a file or table that is organized as a tree structure.
One known search method utilizes a tree to facilitate searching a table stored in the memory of a computer system. This search method forms a tree based on symbols of which the keys are comprised. This is generally referred to as a radix search tree. For example, if the key is comprised of the hexadecimal characters 0 through F, each successive hexadecimal digit position in the key determines 1 of 16 possible children of a given node in the tree.
When the set of keys in a table is sparse, known methods of storing a table of keys in a tree for later radix searching wastes a large amount of memory space. Therefore, there is a need for a way of storing information in a tree structure in the memory of a computer system and for subsequently searching the tree such that the amount of memory required to store a sparse table of keys is minimized. There is a further need for searching a tree in the memory of a computer system in a fast, efficient manner.